How to Tell the Hard From the Impossible